import time
import random

def insertionSort(A):
    for j in range(1,len(A)):
        key = A[j]
        i = j - 1
        while i > -1 and A[i] > key:
            A[i + 1] = A[i]
            i = i - 1
            pass
        A[i + 1] = key
        pass
    return A

    pass

#A = [5, 2, 4, 6, 1, 3]
#print A
#print insertionSort(A)

A = range(1,10000)
random.shuffle(A)
t1 = time.clock()
insertionSort(A)
t2 = time.clock()
print t2-t1
